package com.hyb.algorithm.data.struct.window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: huyanbing
 * @Date: 2021/8/13 8:05 下午
 * <p>
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
 * 438. 找到字符串中所有字母异位词
 * <p>
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindAnagrams {


    public static void main(String[] args) {

//        String s = "cbaebabacd";
//        String p = "abc";

        String s = "abab";
        String p = "ab";

        FindAnagrams findAnagrams = new FindAnagrams();
        List<Integer> res = findAnagrams.findAnagrams(s, p);

        for (Integer t : res) {
            System.out.println(t);
        }
    }

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> res = new ArrayList<>();

        if (s == null || p == null || s.equals("") || p.equals("") || s.length() < p.length()) {
            return res;
        }


        Map<Character, Integer> windows = new HashMap<>();

        Map<Character, Integer> needs = new HashMap<>();

        for (int i = 0; i < p.length(); i++) {
            needs.put(p.charAt(i), needs.getOrDefault(p.charAt(i), 0) + 1);
        }

        int left = 0;
        int right = 0;

        int validCount = 0;

        while (right < s.length()) {

            char charRight = s.charAt(right);

            right++;

            if (needs.containsKey(charRight)) {
                windows.put(charRight, windows.getOrDefault(charRight, 0) + 1);

                if (windows.get(charRight).equals(needs.get(charRight))) {
                    validCount++;
                }
            }


            if (right - left >= p.length()) {

                if (validCount == needs.size()) {
                    res.add(left);
                }

                char charLeft = s.charAt(left);
                left++;

                if (needs.containsKey(charLeft)) {
                    if (windows.get(charLeft).equals(needs.get(charLeft))) {
                        validCount--;
                    }

                    windows.put(charLeft, windows.getOrDefault(charLeft, 0) - 1);
                }
            }


        }

        return res;


    }

}
